package main.java.LeetCode.ClassicalAlgorithm.Tree.Impl;

import main.java.LeetCode.ClassicalAlgorithm.Tree.Iterator.InTreeIterator;
import main.java.LeetCode.ClassicalAlgorithm.Tree.Iterator.PreTreeIterator;
import main.java.LeetCode.ClassicalAlgorithm.Tree.Tree;
import main.java.LeetCode.ClassicalAlgorithm.Tree.TreeIterator;
import main.java.LeetCode.CommonSolution.ListNode;
import main.java.LeetCode.CommonSolution.TreeNode;
import main.java.LeetCode.SolutionVersionThree.Solution;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

@SuppressWarnings("ALL")
public class BinaryTree implements Tree {

    private TreeNode root;

    private final Solution solution = new Solution();

    private TreeIterator iterator;

    public BinaryTree(TreeNode root) {
        this.root = root;
    }

    public BinaryTree() {}

    public BinaryTree(int[] nums) {
        this.root = solution.sortedArrayToBST(nums);
    }

    public BinaryTree(ListNode node) {
        this.root = solution.sortedListToBST(node);
    }

    public TreeNode getRoot() {
        return this.root;
    }

    public void buildTree(int[] nums) {
        this.root = solution.sortedArrayToBST(nums);
    }

    public void buildTree(ListNode head) {
        this.root = solution.sortedListToBST(head);
    }

    public List<List<Integer>> levelOrder() {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) return res;

        ArrayDeque<TreeNode> treeNodes = new ArrayDeque<>();

        treeNodes.add(root);
        int size;

        while (!treeNodes.isEmpty()) {
            size = treeNodes.size();
            LinkedList<Integer> temp = new LinkedList<>();
            while (size != 0) {
                TreeNode node = treeNodes.pop();
                temp.add(node.val);
                size--;
                if (node.left != null) treeNodes.add(node.left);
                if (node.right != null) treeNodes.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }

    public List<Integer> Order(int order) {
        LinkedList<Integer> res = new LinkedList<>();
        oderDfs(root, res, order);
        return res;
    }

    private void oderDfs(TreeNode root, List<Integer> res, int order) {
        if (root == null) return;
        if (order == 0) res.add(root.val);

        oderDfs(root.left, res, order);

        if (order == 1) res.add(root.val);

        oderDfs(root.right, res, order);

        if (order == 2) res.add(root.val);
    }

    public void orderLoopI(TreeNode root) {
        LinkedList<TreeNode> treeNodes = new LinkedList<>();

        while (true) {
            while (root != null) {
                treeNodes.addFirst(root);
                System.out.print(root.val + " ");
                root = root.left;
            }

            if (treeNodes.isEmpty()) break;
            root = treeNodes.pop().right;
        }
    }

    public void orderLoopII(TreeNode root) {
        LinkedList<TreeNode> treeNodes = new LinkedList<>();

        while (true) {
            while (root != null) {
                treeNodes.addFirst(root);
                root = root.left;
            }

            if (treeNodes.isEmpty()) break;
            TreeNode node = treeNodes.pop();
            System.out.print(node.val + " ");
            root = node.right;
        }
    }

    public void orderLoopIII(TreeNode root) {
        LinkedList<TreeNode> treeNodes = new LinkedList<>();

        while (true) {
            while (root != null) {
                treeNodes.addFirst(root);
                root = root.left;
            }

            if (treeNodes.isEmpty()) break;

            TreeNode node = treeNodes.peek();
            if (node.right == null) System.out.print(treeNodes.pop().val + " ");
            else {
                root = node.right;
                node.right = null;
            }
        }
    }

    public void buildTreeByPreOrderAndInOrder(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < preorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        this.root = doBuild(preorder, inMap, 0, 0, preorder.length - 1);
    }

    private TreeNode doBuild(
            int[] pre, HashMap<Integer, Integer> inMap, int rootIndex, int left, int right) {
        if (left > right) return null;

        int nodeVal = pre[rootIndex];
        TreeNode node = new TreeNode(nodeVal);
        if (left < right) {
            int index = inMap.get(nodeVal);
            int leftLength = index - left;

            node.left = doBuild(pre, inMap, rootIndex + 1, left, index - 1);
            node.right = doBuild(pre, inMap, rootIndex + 1 + leftLength, index + 1, right);
        }

        return node;
    }

    public void buildTreeByPostOrderAndInOrder(int[] inorder, int[] postorder) {
        HashMap<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        this.root =
                doBuildForPostOrder(
                        postorder, inMap, postorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode doBuildForPostOrder(
            int[] post, HashMap<Integer, Integer> inMap, int rootIndex, int left, int right) {
        if (left > right) return null;
        int nodeVal = post[rootIndex];
        TreeNode node = new TreeNode(nodeVal);

        if (left < right) {
            int index = inMap.get(nodeVal);
            int rightLength = right - index;

            node.right = doBuildForPostOrder(post, inMap, rootIndex - 1, index + 1, right);
            node.left =
                    doBuildForPostOrder(post, inMap, rootIndex - 1 - rightLength, left, index - 1);
        }
        return node;
    }

    public TreeIterator getIterator() {
        this.iterator = new InTreeIterator(root);
        return iterator;
    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10});

        List<Integer> order = binaryTree.Order(2);
        for (Integer num : order) {
            System.out.print(num + " ");
        }
        System.out.println();
        binaryTree.orderLoopIII(binaryTree.getRoot());
    }
}
